{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Array Partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #counting-sort #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #计数排序 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: arrayPairSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组拆分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定长度为&nbsp;<code>2n</code><strong>&nbsp;</strong>的整数数组 <code>nums</code> ，你的任务是将这些数分成&nbsp;<code>n</code><strong> </strong>对, 例如 <code>(a<sub>1</sub>, b<sub>1</sub>), (a<sub>2</sub>, b<sub>2</sub>), ..., (a<sub>n</sub>, b<sub>n</sub>)</code> ，使得从 <code>1</code> 到&nbsp;<code>n</code> 的 <code>min(a<sub>i</sub>, b<sub>i</sub>)</code> 总和最大。</p>\n",
    "\n",
    "<p>返回该 <strong>最大总和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,4,3,2]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>所有可能的分法（忽略元素顺序）为：\n",
    "1. (1, 4), (2, 3) -&gt; min(1, 4) + min(2, 3) = 1 + 2 = 3\n",
    "2. (1, 3), (2, 4) -&gt; min(1, 3) + min(2, 4) = 1 + 2 = 3\n",
    "3. (1, 2), (3, 4) -&gt; min(1, 2) + min(3, 4) = 1 + 3 = 4\n",
    "所以最大总和为 4</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,2,6,5,1,2]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums.length == 2 * n</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [array-partition](https://leetcode.cn/problems/array-partition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [array-partition](https://leetcode.cn/problems/array-partition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,3,2]', '[6,2,6,5,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        sum =0\n",
    "        for i in range(0,len(nums), 2):\n",
    "            sum+=nums[i]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        s = 0\n",
    "        nums.sort()\n",
    "        n = len(nums) //2\n",
    "        for i in range(n):\n",
    "            mi = min(nums[2*i:2*(i+1)][0],nums[2*i:2*(i+1)][1]) \n",
    "            s += mi \n",
    "        return s\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        return sum([nums[i] for i in range(len(nums)) if i % 2 == 0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return sum(sorted(nums)[::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        return sum(nums[::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(0,len(nums),2):\n",
    "            ans += nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        return sum(sorted(nums)[::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        z=[]\n",
    "        while nums:\n",
    "            z.append(nums[0:2])\n",
    "            nums=nums[2:]\n",
    "        sum=0\n",
    "        for i in z:\n",
    "            sum=sum+min(i)\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        sum1 = 0\n",
    "        while len(nums) > 0:\n",
    "            num1,num2,*nums = nums\n",
    "            sum1 += num1\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        if len(nums)==2:\n",
    "            return min(nums[0],nums[1])\n",
    "        sorted_nums=sorted(nums,key=lambda x:x)\n",
    "        return sum(sorted_nums[0::2])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: 'List[int]') -> 'int':\n",
    "        \n",
    "        nums.sort()\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        i = 0 \n",
    "        \n",
    "        while i < len(nums):\n",
    "            res += nums[i]\n",
    "            i += 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        return sum([nums[i] for i in range(len(nums)) if i % 2 == 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(i%2==0):\n",
    "                res+=nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        nums.sort()\n",
    "        while nums != []:\n",
    "            m = nums.pop()\n",
    "            n = nums.pop()\n",
    "            if n < m:\n",
    "                result = result + n\n",
    "            else:\n",
    "                result = result + m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        while nums:\n",
    "            res += nums[0]\n",
    "            del nums[0]\n",
    "            del nums[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_sum = 0\n",
    "        while nums:\n",
    "            nums_sum += nums.pop(0)\n",
    "            nums.pop(0)\n",
    "        \n",
    "        return nums_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return sum(nums[i] for i in range(0,len(nums),2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return sum([nums[i*2] for i in range(len(nums)//2) ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        a=nums\n",
    "        res=0\n",
    "        while a:\n",
    "            b=nums.pop(0)\n",
    "            c=nums.pop(0)\n",
    "            res+=b\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        while len(nums) > 0:\n",
    "            res += min(nums.pop(),nums.pop())\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        sum = 0\n",
    "        for i in range(len(nums)//2):\n",
    "            n = heapq.heappop(nums)\n",
    "            m = heapq.heappop(nums)\n",
    "            sum += n\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        res = 0\n",
    "        tmp = []\n",
    "        while nums:\n",
    "            tmp.append(nums.pop())\n",
    "            if len(tmp) == 2:\n",
    "                res += min(tmp)\n",
    "                tmp.clear()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        nums.sort()\n",
    "        for i in range(0,len(nums),2):\n",
    "            s = s + nums[i]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        max = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                max += nums[i]\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return sum([nums[2*i] for i in range(len(nums)//2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return sum(nums[::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        while nums:\n",
    "            a = nums.pop()\n",
    "            b = nums.pop()\n",
    "            count += min(a, b)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not i%2:\n",
    "                res += nums[i] \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        rst = 0\n",
    "        for i in sorted(nums)[::2]:\n",
    "        #for i in nums.sort()[::2]:\n",
    "            rst += i\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayPairSum(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        p = 0\n",
    "        sum = 0\n",
    "        while p < len(nums):\n",
    "            sum += nums[p]\n",
    "            p += 2\n",
    "        return sum\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
